package test_314;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 张杰
 * Date: 2022-03-14
 * Time: 16:40
 */
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node(int val) {
        this.val = val;
    }
}
public class BinarySearchTree {
    public Node root = null;

    /* 二叉搜索树，查找结点
     * @author zj
     * @date 2022/3/14
     * @param key
     * @return test_314.Node
    */
    public Node search(int key) {
        Node cur = root;
        while(cur != null) {
            if(cur.val < key) {
                cur = cur.right;
            }else if(cur.val > key) {
                cur = cur.left;
            }else {
                return cur;
            }
        }
        return null;//代表没有这个数据
    }

    /* 二叉搜索树插入结点
     * @author zj
     * @date 2022/3/14
     * @param val
     * @return boolean
    */
    public boolean insert(int val) {
        if(root == null) {
            root = new Node(val);
            return true;
        }
        Node cur = root;
        Node parent = null;
        //确定插入的位置
        while(cur != null) {
            if(cur.val > val) {
                parent = cur;
                cur = cur.left;
            }else if (cur.val == val) {
                return false;
            }else {
                parent = cur;
                cur = cur.right;
            }
        }
        //插入操作
        if(parent.val > val) {
            parent.left = new Node(val);
        }else {
            parent.right = new Node(val);
        }
        return true;
    }

    /* 二叉搜索树，删除结点
     * @author zj
     * @date 2022/3/14
     * @param key
    */
    public void remove(int key) {
        Node cur = root;
        Node parent = null;
        //查找结点
        while(cur != null) {
            if(cur.val == key) {
                //删除操作
                removeNode(cur,parent);
                break;
            }else if(cur.val < key) {
                parent = cur;
                cur = cur.right;
            }else {
                parent = cur;
                cur = cur.left;
            }
        }
    }

    public void removeNode(Node cur,Node parent) {
        //cur是待删除的结点
        if(cur.left == null) {
            if(cur == root) {
                root = cur.right;
            }else if(cur == parent.left) {
                parent.left = cur.right;
            }else {
                parent.right = cur.right;
            }
        }else if(cur.right == null) {
            if(cur == root) {
                root = cur.left;
            }else if(cur == parent.left) {
                parent.left = cur.left;
            }else {
                parent.right = cur.left;
            }
        }else {
            Node tap = cur;
            Node ta = cur.right;
            while(ta.left != null) {
                tap = ta;
                ta = ta.left;
            }
            cur.val = ta.val;
            if(ta == tap.left) {
                tap.left = ta.right;
            }else {
                tap.right = ta.right;
            }

        }
    }

    public void inOrder(Node root) {
        if(root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }

    public static void main(String[] args) {
        int[] array = {13,24,28,17,6,8,19};
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        for (int i = 0; i < array.length; i++) {
            binarySearchTree.insert(array[i]);
        }
        //遍历里面有输出，测试输出需要调中序遍历
        binarySearchTree.inOrder(binarySearchTree.root);
        binarySearchTree.remove(17);
        System.out.println();
        binarySearchTree.inOrder(binarySearchTree.root);
    }
}
